package model;

import ilog.concert.IloException;
import ilog.concert.IloLinearNumExpr;
import ilog.concert.IloNumVar;
import ilog.cplex.IloCplex;

public class TSP {
	int n = 0;
	IloCplex modeler = null;
	static String MPSFILE = "TSP.mps";

	public TSP(int numberOfCities)
	{
		n = numberOfCities;
		try {
			modeler = new IloCplex();
		} catch (IloException e) {
			e.printStackTrace();
		}
	}
	
	public void createModel()
	{  
		double[] xPos = new double[n];
		double[] yPos = new double[n];
		
		for (int i = 0; i < n; i++) {
			xPos[i] = Math.random()*100;
			yPos[i] = Math.random()*100;
		}
		
		double[][] c = new double[n][n];
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (i==j)
				{
					c[i][j] = 0;
				}
				else
				{
					c[i][j] = Math.sqrt(Math.pow(xPos[i]-xPos[j], 2) + Math.pow(yPos[i]-yPos[j], 2));
				}
			}
		}
		
		try{
			IloNumVar x[][] = new IloNumVar[n][];
			
			for (int i = 0; i < n; i++) {
				x[i] = modeler.boolVarArray(n);
			}
			
			IloNumVar u[] = modeler.numVarArray(n, 0, Double.MAX_VALUE);
			
			//add objective
			IloLinearNumExpr obj = modeler.linearNumExpr();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n; j++) {
					if (i!=j)
					{
						obj.addTerm(c[i][j],x[i][j]);
					}
				}
			}
			modeler.addMinimize(obj);
			
			//add constraints
			for (int i = 0; i < n; i++) {
				IloLinearNumExpr expr = modeler.linearNumExpr();
				for (int j = 0; j < n; j++) {
					if (i!=j)
					{
						expr.addTerm(1.0,x[i][j]);
					}
				}
				modeler.addEq(expr,1.0);
			}
			
			for (int j = 0; j < n; j++) {
				IloLinearNumExpr expr = modeler.linearNumExpr();
				for (int i = 0; i < n; i++) {
					if (i!=j)
					{
						expr.addTerm(1.0,x[i][j]);
					}
				}
				modeler.addEq(expr,1.0);
			}
			
			for (int i = 1; i < n; i++) {
				for (int j = 1; j < n; j++) {
					if (i!=j)
					{
						IloLinearNumExpr expr = modeler.linearNumExpr();
						expr.addTerm(1.0,u[i]);
						expr.addTerm(-1.0,u[j]);
						expr.addTerm(n-1,x[i][j]);
						modeler.addLe(expr,n-2);
					}
				}
			}
		}
		catch(IloException e)
		{
			e.printStackTrace();
		}
		
	}
	
	public void saveMPS()
	{
		try {
			modeler.exportModel(MPSFILE);
		} catch (IloException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	}
	
	 static public void main(String[] args)
	{
		 TSP problem = new TSP(200);
		 problem.createModel();
		 problem.saveMPS();
		 System.out.println("Done!");
	}
}

